package com.sakura.双指针;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

// 给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，
// 请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。
public class Code02_统计和小于目标的下标对数目 {

    // 暴力做法只需要两个for就好
    // 双指针：
    //    数据有序和无序对答案并没有影响  [-1, 2] = 1 [2, -1] = 1
    //    因此我们先排序。
    //    当 num[left] + num[right] < target 时，说明 [left + 1, right] 的元素都满足条件（因为有序）
    public int countPairs_1(List<Integer> nums, int target) {
        nums.sort((Comparator.comparingInt(o -> o)));
        int left = 0;
        int right = nums.size() - 1;
        int ans = 0;
        while (left < right) {
            if (nums.get(left) + nums.get(right) < target) {
                ans += right - left;
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }


    public int countPairs_2(List<Integer> nums, int target) {
        Collections.sort(nums);
        int left = 0;
        int right = nums.size() - 1;
        int ans = 0;
        while (left < right) {
            while (left < right && nums.get(left) + nums.get(right) >= target) {
                right--;
            }
            ans += right - left;
            left++;
        }
        return ans;
    }
}
